package A一周刷爆LeetCode.A基础班.C认识NlogN的排序;

import java.util.Objects;

/**
 * @author wei.zhao
 * @description: 逆序对问题
 * @date 2022年01月13日 11:42
 */
public class Code03_InversionPair {

    public static int inversionPair(int[] arr) {
        if (Objects.isNull(arr) || arr.length < 2) {
            return -1;
        }
        int i = mergeSort(arr, 0, arr.length - 1);
        return i;
    }

    private static int mergeSort(int[] arr, int l, int r) {
        if (l == r) {
            return 0;
        }
        int mid = l + ((r - l) >> 1);
        return mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r) + merge(arr, l, mid, r);
    }

    private static int merge(int[] arr, int l, int mid, int r) {
        int result = 0;
        int lp = l;
        int rp = mid + 1;
        int[] temp = new int[r - l + 1];
        for (int i = 0; i < temp.length; i++) {
            if (lp > mid) {
                //左边溢出
                temp[i] = arr[rp++];
            } else if (rp > r) {
                //右边溢出
                temp[i] = arr[lp++];
            } else if (arr[lp] <= arr[rp]) {
                //右边较大
                temp[i] = arr[lp++];
            } else if (arr[lp] > arr[rp]) {
                //左边较大
                temp[i] = arr[rp++];
                result += mid - lp + 1;
            }
        }
        for (int i = 0; i < temp.length; i++) {
            arr[l + i] = temp[i];
        }
        return result;
    }

}
